package rob;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Solution {
    public int rob(int[] nums) {
        //
        int n = nums.length;
        return Math.max(fun(nums,0,n-1),fun(nums,1,n));
    }
    private int fun(int[] nums,int start,int end) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[start] = nums[start];
        if(start+1>=end)return nums[start];
        dp[start+1] = Math.max(nums[start],nums[start+1]);
        for (int i = start+2; i < end; i++) {
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[end-1];
    }

}
